package solutions.leetcode.hard;

import solutions.lib.BaseSolution;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/k-inverse-pairs-array/">629. K个逆序对数组</a>
 */
public class Solution629 extends BaseSolution {

    public int kInversePairs(int n, int k) {
        if (k == 0) {
            return 1;
        }
        int mod = 1000000007;
        int[][] flag = new int[2][k];
        int p = 0;
        while (p ++ < n - 1) {
            int sum = 0;
            int[] last = flag[p % 2];
            int[] next = flag[(p + 1) % 2];
            for (int i = 0; i < k; i++) {
                long temp = last[i] - (i - p - 1 >= 0 ? last[i - p - 1] : 0) + sum;
                sum = (int) ((temp + mod) % mod);
                if (i < p) {
                    next[i] = i == 0 ? p : next[i - 1] + last[i];
                    next[i] %= mod;
                } else {
                    next[i] = sum;
                }
            }
        }
        return flag[n % 2][k - 1];
    }

    public static void main(String[] args) {
        Solution629 solution = new Solution629();
        System.out.println(solution.kInversePairs(1000, 1000));
    }
}